import java.util.Arrays;

public class Solution1011 {
    int[] prefixArr;

    public int getRangeSum(int start,int end){
        return prefixArr[end]-prefixArr[start];
    }

    public int shipWithinDays(int[] weights, int D) {
        if(weights.length<=D){
            return Arrays.stream(weights).max().getAsInt();
        }

        prefixArr=new int[weights.length];
        int sum=0;
        for (int i = 0; i < weights.length; i++) {
            sum+=weights[i];
            prefixArr[i]=sum;
        }

        int[][] DP=new int[weights.length][D+1];
        for (int i = 0; i < weights.length; i++) {
            DP[i][1]=prefixArr[i];
        }
        for (int i = 1; i < weights.length; i++) {
            for (int j = 2; j <= Math.min(D,i+1); j++) {
                int small=Integer.MAX_VALUE;
                for (int k = 0; k < i; k++) {
                    int tmpNum=j-1;
                    int befSum=DP[k][tmpNum];
                    int aftSum=getRangeSum(k,i);
                    small=Math.min(small,Math.max(befSum,aftSum));
                }
                DP[i][j]=small;
            }
        }
        return DP[weights.length-1][D];
    }

    public static void main(String[] args) {
        Solution1011 s=new Solution1011();
        System.out.println(s.shipWithinDays(new int[]{1,2,3,4,5,6,7,8,9,10},5));
    }
}
